package com.zhaofan.interview;




import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/list-of-depth-lcci/
 */
public class No0403 {
    TreeNode root;

    public static void main(String[] args) {
        No0403 no0304 = new No0403();
        Integer[] a=new Integer[]{1,2,3,4,5,null,7,8};
        no0304.insert(a);
        ListNode[] listNodes = no0304.listOfDepth(no0304.root);
        Arrays.stream(listNodes).forEach((node)->{
            while(node!=null){
                System.out.print(node.val+",");
                node=node.next;
            }
            System.out.println();
        });



    }


    public void insert(Integer[] a){
        if(a.length==0 ) return;
        if(root==null){
            root=new TreeNode(a[0]);
        }

        LinkedList<TreeNode> list = new LinkedList<>();
        list.push(root);
        for (int i = 1; i < a.length; i++) {
            TreeNode node = list.peek();
            if(node==null){
                i--;
                continue;
            }
            if(i%2==1){
                if(node.left!=null){
                    list.add(node.left);
                    i--;
                }else{
                    if(a[i]==null){
                        node.left=null;
                    }else{
                        node.left = new TreeNode(a[i]);
                        list.add(node.left);
                    }
                }
            }else{
                if(node.right!=null){
                    list.add(node.right);
                    --i;
                }else{
                    if(a[i]==null){
                        node.right=null;
                    }else{
                        node.right=new TreeNode(a[i]);
                        list.add(node.right);
                    }

                }
                list.poll();
            }
        }
    }



    public ListNode[] listOfDepth(TreeNode tree) {
        LinkedList<TreeNode> list = new LinkedList<>();
//        list.add(null);
        list.add(tree);
        list.add(null);
        ArrayList<ListNode> result = new ArrayList<>();
        ListNode listNode=null,tmp=null;
        while(!list.isEmpty()){
            TreeNode node = list.removeFirst();
            if(node==null&&list.size()==0){
                break;
            }else if(node==null){
                list.add(null);
                continue;
            }

            if(node.left!=null){
                list.add(node.left);
            }
            if(node.right!=null){
                list.add(node.right);
            }

            if(listNode==null){
                listNode=new ListNode(node.val);
                tmp=listNode;
            }else {
                tmp.next=new ListNode(node.val);
                tmp=tmp.next;
            }

            if(list.getFirst()==null){
                result.add(listNode);
                listNode=null;

            }
        }
        return result.toArray(new ListNode[result.size()]);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
}
